package learn.linkedListImpl;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_ADDPeer;

import java.util.List;

/**
 * 自定义单链表
 *这道题目设计链表的五个接口：
 *
 * 获取链表第index个节点的数值
 * 在链表的最前面插入一个节点
 * 在链表的最后面插入一个节点
 * 在链表第index个节点前面插入一个节点
 * 删除链表的第index个节点
 * 可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目
 *
 * 链表操作的两种方式：
 *
 * 直接使用原来的链表来进行操作。
 * 设置一个虚拟头结点在进行操作。
 * */

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
}

/**
 * 构造自定义链表
 */
public class MyLinkedList {
    //链表长度
    int size;
    //头节点
    ListNode head;

    MyLinkedList() {
        this.size = 0;
        head = new ListNode();
    }

    //获取链表第index个节点的数值
    public int getIndex(int index) {
        if (index < 0 || index > size) {
            return -1;
        }

        ListNode current = head;

        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }

    //在链表的最后面插入一个节点
    public void addAtTail(int val) {
        //前驱指针后一到单链表最后面
        ListNode pred = head;
        for (int i = 0; i < this.size; i++) {
            pred = pred.next;
        }
        this.size++;
        //插入先创建结点
        ListNode listNode = new ListNode(val);
        pred.next = listNode;
    }

    //在链表的最前面插入一个节点
    public void addAtHead(int val){
        //头插法
        //创建新的节点
        ListNode listNode = new ListNode(val);
        listNode.next = head.next;
        head.next = listNode;
        this.size++;
    }

    //在链表第index个节点前面插入一个节点
    public void addIndex(int index,int val){
        if (index<0 || index>=size){
            return;
        }
        //首先找到第index节点指针
        ListNode current = head;
        for (int i=1;i<index;i++){
            current = current.next;
        }
        //创建新的节点
        ListNode listNode = new ListNode(val);
        listNode.next = current.next;
        current.next = listNode;
        this.size++;
    }

    //删除链表的第index个节点
    public void deleteIndex(int index){
        if (index<0||index>size){
            return;
        }
        ListNode current = head;
        //将指针执行前一个节点
        for (int i=1;i<index;i++){
           current = current.next;
        }
        ListNode afterNode = current.next.next;
        current.next = afterNode;
        size--;
    }





    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtTail(3);
        myLinkedList.addAtTail(4);
        myLinkedList.addAtTail(5);
        myLinkedList.addAtTail(6);
        //myLinkedList.addAtHead(7);
        //myLinkedList.addIndex(3,100);
        myLinkedList.deleteIndex(2);
        System.out.println(myLinkedList.getIndex(4));

    }
}





























